// 138.复制带随机指针的链表

package Leetcode;

import java.util.HashMap;
import java.util.Map;

// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution138 {
    public Node copyRandomList(Node head) {
        // Node headCopy = head;
        // Node node = new Node(0);
        // Node pre = node;
        // while (head != null) {
        // Node newNode = new Node(head.val);
        // node.next = newNode;
        // node = node.next;
        // head = head.next;
        // }
        // while (pre != null) {
        // System.out.println(pre.val);
        // pre = pre.next;
        // }
        // return head;

        // ArrayList<Node> nodeList = new ArrayList<>();
        // ArrayList<Integer> pointerList = new ArrayList<>();
        // while (head != null) {
        // nodeList.add(new Node(head.val));
        // pointerList.add(head.val);
        // head = head.next;
        // }
        // for (int i = 0; i < pointerList.size(); i++) {
        // if (i + 1 < pointerList.size())
        // nodeList.get(i).next = nodeList.get(i + 1);
        // if (i + 1 == pointerList.size())
        // nodeList.get(i).next = null;

        // }

        // 使用map进行深拷贝
        Map<Node, Node> map = new HashMap<>();
        Node headCopy = head; //用于多次遍历
        // 第一次遍历仅创建副本
        while (head != null) {
            map.put(head, new Node(head.val));
            head = head.next;
        }
        // 第二次遍历复制next和random指针信息
        head = headCopy;
        while (head != null) {
            // next指针
            map.get(head).next = map.get(head.next);
            // random指针
            if (head.random == null)
                map.get(head).random = null;
            else
                map.get(head).random = map.get(head.random);
            head = head.next;
        }
        return map.get(headCopy);
    }
}
